{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Longest Increasing Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #segment-tree #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #线段树 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findNumberOfLIS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长递增子序列的个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个未排序的整数数组<meta charset=\"UTF-8\" />&nbsp;<code>nums</code>&nbsp;，&nbsp;<em>返回最长递增子序列的个数</em>&nbsp;。</p>\n",
    "\n",
    "<p><strong>注意</strong>&nbsp;这个数列必须是 <strong>严格</strong> 递增的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> [1,3,5,4,7]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> [2,2,2,2,2]\n",
    "<strong>输出:</strong> 5\n",
    "<strong>解释:</strong> 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 2000</code></li>\n",
    "\t<li><code>-10<sup>6</sup>&nbsp;&lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-longest-increasing-subsequence](https://leetcode.cn/problems/number-of-longest-increasing-subsequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-longest-increasing-subsequence](https://leetcode.cn/problems/number-of-longest-increasing-subsequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,5,4,7]', '[2,2,2,2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n, max_len, ans = len(nums), 0, 0\n",
    "        dp = [0]*n\n",
    "        cnt = [0]*n\n",
    "        for i, x in enumerate(nums):\n",
    "            dp[i] = 1\n",
    "            cnt[i] = 1\n",
    "            for j in range(i):\n",
    "                if x > nums[j]:\n",
    "                    if dp[j]+1 > dp[i]:\n",
    "                        dp[i] = dp[j]+1\n",
    "                        cnt[i] = cnt[j]\n",
    "                    elif dp[j]+1 == dp[i]:\n",
    "                        cnt[i] += cnt[j]\n",
    "            if dp[i] > max_len:\n",
    "                max_len = dp[i]\n",
    "                ans = cnt[i]\n",
    "            elif dp[i] == max_len:\n",
    "                ans += cnt[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        ls=len(nums)\n",
    "        countn=[0]*ls\n",
    "        maxn=[0]*ls\n",
    "\n",
    "        for i in range(ls):\n",
    "            if i==0:\n",
    "                countn[i]=1\n",
    "                maxn[i]=1\n",
    "            else:\n",
    "                tem=[(countn[j]+1,j) for j in range(i) if nums[j]<nums[i]]\n",
    "\n",
    "                if tem:\n",
    "                    temmax,temn=0,0\n",
    "                    for m,n in tem:\n",
    "                        if m>temmax:\n",
    "                            temmax=m\n",
    "                            temn=maxn[n]\n",
    "                        elif m==temmax:\n",
    "                            temn+=maxn[n]\n",
    "                    countn[i]=temmax\n",
    "                    maxn[i]=temn\n",
    "                \n",
    "                else:\n",
    "                    countn[i]=1\n",
    "                    maxn[i]=1\n",
    "        \n",
    "        return sum([maxn[i] for i in range(ls) if countn[i]==max(countn)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class MaximumSegmentTree:\n",
    "    def __init__(self, nums):\n",
    "        n = len(nums)\n",
    "        self.d = [0] * (4 * n)\n",
    "        self.b = [0] * (4 * n)\n",
    "        self.n = n\n",
    "        self.build([0] + nums, 1, n, 1)\n",
    "\n",
    "    def build(self, a, s, t, p):\n",
    "        d, b = self.d, self.b\n",
    "        if s == t:\n",
    "            d[p] = a[s]\n",
    "            return\n",
    "        m = (s + t) // 2\n",
    "        self.build(a, s, m, 2 * p)\n",
    "        self.build(a, m + 1, t, 2 * p + 1)\n",
    "        d[p] = max(d[2 * p], d[2 * p + 1])\n",
    "\n",
    "    def push_down(self, s, t, p):\n",
    "        d, b = self.d, self.b\n",
    "        if b[p] and s != t:\n",
    "            d[2 * p] += b[p]\n",
    "            d[2 * p + 1] += b[p]\n",
    "            b[2 * p] += b[p]\n",
    "            b[2 * p + 1] += b[p]\n",
    "            b[p] = 0\n",
    "\n",
    "    def _update(self, l, r, c, s, t, p):\n",
    "        d, b = self.d, self.b\n",
    "        if c == 0:\n",
    "            return\n",
    "        if l <= s <= t <= r:\n",
    "            d[p] += c\n",
    "            b[p] += c\n",
    "            return\n",
    "        m = (s + t) // 2\n",
    "        self.push_down(s, t, p)\n",
    "        if l <= m:\n",
    "            self._update(l, r, c, s, m, 2 * p)\n",
    "        if m < r:\n",
    "            self._update(l, r, c, m + 1, t, 2 * p + 1)\n",
    "        d[p] = max(d[2 * p], d[2 * p + 1])\n",
    "\n",
    "    def update(self, l, r, c):\n",
    "        self._update(l + 1, r + 1, c, 1, self.n, 1)\n",
    "\n",
    "    def _get_max(self, l, r, s, t, p):\n",
    "        d, b = self.d, self.b\n",
    "        if l <= s <= t <= r:\n",
    "            return d[p]\n",
    "        self.push_down(s, t, p)\n",
    "        m = (s + t) // 2\n",
    "        max_ = -10**10\n",
    "        if l <= m:\n",
    "            max_ = max(max_, self._get_max(l, r, s, m, 2 * p))\n",
    "        if m < r:\n",
    "            max_ = max(max_, self._get_max(l, r, m + 1, t, 2 * p + 1))\n",
    "        return max_\n",
    "\n",
    "    def get_max(self, l, r):\n",
    "        return self._get_max(l+1, r+1, 1, self.n, 1)\n",
    "\n",
    "    def _get_max_indices(self, l, r, s, t, p, max_value, indices):\n",
    "        d, b = self.d, self.b\n",
    "        self.push_down(s, t, p)\n",
    "        if s == t:\n",
    "            if d[p] == max_value:\n",
    "                indices.append(s)\n",
    "            return\n",
    "\n",
    "        m = (s + t) // 2\n",
    "        if l <= m and d[2*p] + b[p] >= max_value:\n",
    "            self._get_max_indices(l, r, s, m, 2 * p, max_value, indices)\n",
    "        if m < r and d[2*p+1] + b[p] >= max_value:\n",
    "            self._get_max_indices(l, r, m + 1, t, 2 * p + 1, max_value, indices)\n",
    "\n",
    "    def get_max_indices(self, l, r, max_value, indices):\n",
    "        _indices =[]\n",
    "        self._get_max_indices(l+1, r+1, 1, self.n, 1, max_value, _indices)\n",
    "        indices.extend(x-1 for x in _indices)\n",
    "        return indices\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: list[int]) -> int:\n",
    "        uniq_values = set(nums)\n",
    "        num_map = {num: i + 1 for i, num in enumerate(sorted(uniq_values))}\n",
    "        nums = [0] + [num_map[num] for num in nums]\n",
    "        n = len(uniq_values) + 1\n",
    "\n",
    "        lis_lens = [0] * n\n",
    "        lis_lens[0] = 1\n",
    "        lis_cnts = [0] * n\n",
    "        lis_cnts[0] += 1\n",
    "        segment_tree = MaximumSegmentTree(lis_lens)\n",
    "        segment_tree.update(0, 0, 1)\n",
    "\n",
    "        for num in nums[1:]:\n",
    "            prev_lis_len = segment_tree.get_max(0, num - 1)\n",
    "            prev_nums = []\n",
    "            segment_tree.get_max_indices(0, num - 1, max_value=prev_lis_len, indices=prev_nums)\n",
    "            if lis_lens[num] == prev_lis_len + 1:\n",
    "                lis_cnts[num] += sum(lis_cnts[prev_num] for prev_num in prev_nums)\n",
    "            else:\n",
    "                diff = prev_lis_len + 1 - lis_lens[num]\n",
    "                segment_tree.update(num, num, diff)\n",
    "                lis_cnts[num] = sum(lis_cnts[prev_num] for prev_num in prev_nums)\n",
    "                lis_lens[num] = prev_lis_len + 1\n",
    "\n",
    "        max_lis_len = max(lis_lens)\n",
    "        max_lis_len_cnt = sum(lis_cnt for lis_len, lis_cnt in zip(lis_lens, lis_cnts) if lis_len == max_lis_len)\n",
    "        return max_lis_len_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #10:41-10:55 wrong\n",
    "    def findNumberOfLIS(self, A: List[int]) -> int:\n",
    "        cnt = defaultdict(lambda:0)\n",
    "        n = len(A)\n",
    "        top = [A[0]]\n",
    "        cnt[1] = 1\n",
    "        for i in range(1,n):\n",
    "            if A[i]==top[-1]:\n",
    "                cnt[len(top)] += 1\n",
    "            elif A[i]>top[-1]:\n",
    "                top.append(A[i])\n",
    "                cnt[len(top)] += 1\n",
    "            else:\n",
    "                l = bisect_left(top,A[i])\n",
    "                top[l] = A[i]\n",
    "                cnt[l] += 1\n",
    "        print(cnt)\n",
    "        print(top)\n",
    "        ans = 1\n",
    "        for k,v in cnt.items():\n",
    "            ans *= v\n",
    "        return ans\n",
    "\n",
    "    #1102\n",
    "    def findNumberOfLIS(self, A: List[int]) -> int:\n",
    "        n = len(A)\n",
    "        dp = [ [1,1] for _ in range(n)]\n",
    "        longest = 1\n",
    "        for i in range(1,n):\n",
    "            for j in range(i):\n",
    "                if A[i]>A[j]:\n",
    "                    if dp[i][0]<dp[j][0] + 1:#拼接之后序列更长，序列个数复制之前\n",
    "                        dp[i][0] = dp[j][0] + 1\n",
    "                        longest = max(longest, dp[i][0])\n",
    "                        dp[i][1] = dp[j][1] \n",
    "                    elif dp[i][0] == dp[j][0]+1:#拼接之后序列一样长，序列个数累加\n",
    "                        dp[i][1] += dp[j][1]\n",
    "        return sum( dp[i][1] for i in range(n) if dp[i][0]==longest)\n",
    "\n",
    "def bisect(n: int, f: Callable[[int], bool]) -> int:\n",
    "    l, r = 0, n\n",
    "    while l < r:\n",
    "        mid = (l + r) // 2\n",
    "        if f(mid):\n",
    "            r = mid \n",
    "        else:\n",
    "            l = mid + 1\n",
    "    return l\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        d, cnt = [], []\n",
    "        for v in nums:\n",
    "            i = bisect(len(d), lambda i: d[i][-1] >= v)\n",
    "            c = 1\n",
    "            if i > 0:\n",
    "                k = bisect(len(d[i - 1]), lambda k: d[i - 1][k] < v)#v比前一堆大的牌的个数\n",
    "                c = cnt[i - 1][-1] - cnt[i - 1][k]\n",
    "            if i == len(d):\n",
    "                d.append([v])\n",
    "                cnt.append([0, c])\n",
    "            else:\n",
    "                d[i].append(v)\n",
    "                cnt[i].append(cnt[i][-1] + c)\n",
    "        return cnt[-1][-1]\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def findNumberOfLIS(self, nums):\n",
    "        import bisect\n",
    "        dp = []\n",
    "        tree = collections.defaultdict(list)\n",
    "        for i in nums:\n",
    "            idx = bisect.bisect_left(dp,i)\n",
    "            if idx == len(dp):\n",
    "                dp.append(i)\n",
    "            else:\n",
    "                dp[idx] = i\n",
    "            total = 0\n",
    "            for counter, last_num in tree[idx]:\n",
    "                if last_num < i:\n",
    "                    total += counter\n",
    "            tree[idx+1].append((max(1,total), i))\n",
    "        return sum(i[0] for i in tree[len(tree)-1])#最后把最长路径的各个叶子节点数目加一块就出来了\n",
    "\n",
    "def bisect(n,f):\n",
    "    l,r = 0,n\n",
    "    while l<r:\n",
    "        m = l+r>>1\n",
    "        if f(m):r = m\n",
    "        else: l = m+1\n",
    "    return l \n",
    "class Solution(object):\n",
    "    def findNumberOfLIS(self, A):\n",
    "        d = []  #d[i][j]   表示第i堆的第j张牌\n",
    "        c = []#cnt[i][j] 表示以第i堆第j张牌为结尾的最长递增序列数\n",
    "        for v in A:\n",
    "            i = bisect(len(d),lambda i:d[i][-1]>=v)\n",
    "            cnt = 1\n",
    "            if i>0:\n",
    "                k = bisect(len(d[i-1]), lambda k:d[i-1][k]<v)\n",
    "                cnt = c[i-1][-1] - c[i-1][k]\n",
    "            if i==len(d):\n",
    "                d.append([v])\n",
    "                c.append([0,cnt])\n",
    "            else:\n",
    "                d[i].append(v)\n",
    "                c[i].append(c[i][-1]+cnt)#构造前缀和\n",
    "        return c[-1][-1]\n",
    "\n",
    "class Solution2:#时间击败100%\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        贪心 + 二分查找 + 前缀和。LeetCode题300方法二的进阶\n",
    "        将数组d扩展为二维数组，其中d[i]是一个一维数组，d[i]中包含所有长度为i的最长递增子序列的末尾元素值，可以发现，d[i]是单调递减的，\n",
    "        因为从前往后遍历nums的过程中，如果某个num大于d[i][j]，那么这个num就不会作为长度为i的最长递增子序列的末尾元素值，\n",
    "        而是会作为长度为i + 1的最长递增子序列的末尾元素值，即 append到d[i+1]数组中。所以只有小于等于d[i][j]的num，才有可能会append到d[i]数组。\n",
    "        因此，对于当前num，可通过二分查找的方式，在二维数组d中找到第一个满足末尾元素大于等于当前num的子数组d[i]，即 d[i-1][-1] < num <= d[i][-1]，\n",
    "        然后在d[i-1]中通过二分查找第一个小于当前num的元素下标k，即 d[i-1][k] ~ d[i-1][-1] 中的所有元素都小于当前num，\n",
    "        这些元素中的每一个都可以和当前num组成长度为i的最长递增子序列。\n",
    "        由上可知，二维数组d中的所有子数组，它们的末尾元素满足严格单调递增；而每个子数组内部，又满足单调递减。\n",
    "        类似的，再定义一个对应的二维数组cnt，cnt[i][j]记录了以d[i][j]结尾的最长递增子序列的个数。\n",
    "        对于上面所有小于当前num(d[i][j])的d[i-1][k] ~ d[i-1][-1]，它们对应的cnt[i-1][k] ~ cnt[i-1][-1]累加，就得到了cnt[i][j]。\n",
    "        为方便计算cnt[i-1][k] ~ cnt[i-1][-1]的累加和，可将cnt改为前缀和，即 二维数组cnt中的每一个子数组都是前缀和数组，每个前缀和数组的开头元素均为0\n",
    "        这样一来，最终返回结果就是 cnt[-1][-1]\n",
    "        对于nums中的每个元素，二分查找的次数为：至少一次、至多两次。所以时间复杂度为O(nlogn)\n",
    "        \"\"\"\n",
    "        d, cnt = [], []\n",
    "        for num in nums:\n",
    "            if not d:\n",
    "                d.append([num])\n",
    "                # cnt中的各个子数组的开头元素均为0\n",
    "                cnt.append([0, 1])\n",
    "            elif d[-1][-1] < num:\n",
    "                left, right = 0, len(d[-1]) - 1\n",
    "                # 在单调递减数组d[-1]中，二分查找第一个小于当前num的元素下标k。已知，d[-1][-1] < num，所以k一定存在\n",
    "                while left < right:\n",
    "                    mid = (left + right) // 2\n",
    "                    if d[-1][mid] < num:\n",
    "                        right = mid\n",
    "                    else:\n",
    "                        left = mid + 1\n",
    "                # 二维数组d的长度与二维数组cnt的长度相等，不过，cnt中的各个子数组长度都比d中对应的各个子数组长度大1，\n",
    "                # 因为cnt中的各个子数组都在开头添加了一个0，为了方便计算前缀和\n",
    "                c = cnt[-1][-1] - cnt[-1][left]\n",
    "                d.append([num])\n",
    "                cnt.append([0, c])\n",
    "            else:\n",
    "                left, right = 0, len(d) - 1\n",
    "                # 二维数组d中的所有子数组，它们的末尾元素满足严格单调递增，二分查找第一个满足末尾元素大于等于当前num的子数组下标i\n",
    "                # 已知，d[-1][-1] >= num，所以i一定存在\n",
    "                while left < right:\n",
    "                    mid = (left + right) // 2\n",
    "                    if d[mid][-1] >= num:\n",
    "                        right = mid\n",
    "                    else:\n",
    "                        left = mid + 1\n",
    "                i = left\n",
    "                c = 1\n",
    "                if i > 0:\n",
    "                    # 在单调递减数组d[i-1]中，二分查找第一个小于当前num的元素下标k。已知，d[i-1][-1] < num，所以k一定存在\n",
    "                    left, right = 0, len(d[i - 1]) - 1\n",
    "                    while left < right:\n",
    "                        mid = (left + right) // 2\n",
    "                        if d[i - 1][mid] < num:\n",
    "                            right = mid\n",
    "                        else:\n",
    "                            left = mid + 1\n",
    "                    c = cnt[i - 1][-1] - cnt[i - 1][left]\n",
    "                d[i].append(num)\n",
    "                # 注意：二维数组cnt中的每一个子数组都是前缀和数组，所以这里append的是cnt[i][-1] + c，而不是c\n",
    "                cnt[i].append(cnt[i][-1] + c)\n",
    "        return cnt[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        dp = [1]*len(nums)\n",
    "        count = [1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(0,i):\n",
    "                if nums[j]<nums[i]:\n",
    "                    if dp[j]+1>dp[i]:\n",
    "                        dp[i] = dp[j]+1\n",
    "                        count[i] = count[j]\n",
    "                    elif dp[j]+1==dp[i]:\n",
    "                        count[i] +=count[j]\n",
    "        print(dp)\n",
    "        print(count)\n",
    "        maxN = max(dp)\n",
    "        res = 0\n",
    "        for i in range(len(dp)):\n",
    "            if dp[i] == maxN:\n",
    "                res += count[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        # dp[i]表示以nums[i]结尾的最长上升子序列的长度\n",
    "        # cnt[i]表示以nums[i]结尾的最长上升子序列的个数\n",
    "        n = len(nums)\n",
    "        maxLen = 0\n",
    "        res = 0\n",
    "        dp = [0] * n\n",
    "        cnt = [0] * n\n",
    "        for i in range(n):\n",
    "            dp[i] = 1\n",
    "            cnt[i] = 1\n",
    "            x = nums[i]\n",
    "            for j in range(i):\n",
    "                if x > nums[j]:\n",
    "                    if dp[j] + 1 > dp[i]:\n",
    "                        dp[i] = dp[j] + 1\n",
    "                        # 重置计数\n",
    "                        cnt[i] = cnt[j]\n",
    "                    elif dp[j] + 1 == dp[i]:\n",
    "                        cnt[i] += cnt[j]\n",
    "            if dp[i] > maxLen:\n",
    "                maxLen = dp[i]\n",
    "                # 重置计数\n",
    "                res = cnt[i]\n",
    "            elif dp[i] == maxLen:\n",
    "                res += cnt[i]\n",
    "        # 返回最长递增子序列的个数\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        # cnt=collections.defaultdict(int)\n",
    "        dp=[1]*len(nums)\n",
    "        cnt=[1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i):\n",
    "                if nums[j]<nums[i]:\n",
    "                    if dp[j]+1>dp[i]:\n",
    "                        dp[i]=dp[j]+1\n",
    "                        cnt[i]=cnt[j]\n",
    "                    elif dp[j]+1==dp[i]:\n",
    "                        cnt[i]+=cnt[j]\n",
    "        tmp=max(dp)\n",
    "        res=0\n",
    "        for i in range(len(dp)):\n",
    "            if dp[i]==tmp:\n",
    "                res+=cnt[i]\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        dp = [1]*len(nums)\n",
    "        count = [1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(0,i):\n",
    "                if nums[j]<nums[i]:\n",
    "                    if dp[j]+1>dp[i]:\n",
    "                        dp[i] = dp[j]+1\n",
    "                        count[i] = count[j]\n",
    "                    elif dp[j]+1==dp[i]:\n",
    "                        count[i] +=count[j]\n",
    "       \n",
    "        maxN = max(dp)\n",
    "        res = 0\n",
    "        for i in range(len(dp)):\n",
    "            if dp[i] == maxN:\n",
    "                res += count[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp1 = [1] * n\n",
    "        dp2 = [1] * n\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    if dp1[j] + 1 > dp1[i]:\n",
    "                        dp1[i] = dp1[j] + 1\n",
    "                        dp2[i] = dp2[j]\n",
    "                    elif dp1[j] + 1 == dp1[i]:\n",
    "                        dp2[i] += dp2[j]\n",
    "        maxval = max(dp1)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if dp1[i] == maxval:\n",
    "                res += dp2[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        seq = [1]*len(nums)\n",
    "        cnt = [0]*len(nums)\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i):\n",
    "                if nums[j]<nums[i]:      \n",
    "                    seq[i] = max(seq[i],seq[j]+1)\n",
    "            if seq[i] == 1:\n",
    "                cnt[i] = 1\n",
    "                continue\n",
    "            c = 0\n",
    "            for j in range(i):\n",
    "                if nums[j]<nums[i] and seq[j] == seq[i]-1:\n",
    "                    c += cnt[j]\n",
    "            cnt[i] = c\n",
    "\n",
    "        mx = max(seq)\n",
    "        ret = 0\n",
    "        for i in range(len(nums)):\n",
    "            if seq[i] == mx:\n",
    "                ret += cnt[i]\n",
    "        # print(seq)\n",
    "        # print(cnt)\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        cnt = [0] * n\n",
    "        max_len = 0\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i] = 1\n",
    "            cnt[i] = 1\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i]:\n",
    "                    if dp[j] + 1 > dp[i]:\n",
    "                        dp[i] = dp[j] + 1\n",
    "                        cnt[i] = cnt[j]  # 重置计数\n",
    "                    elif dp[j] + 1 == dp[i]:\n",
    "                        cnt[i] += cnt[j]\n",
    "            if dp[i] > max_len:\n",
    "                max_len = dp[i]\n",
    "                ans = cnt[i]  # 重置计数\n",
    "            elif dp[i] == max_len:\n",
    "                ans += cnt[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n, max_len, ans = len(nums), 0, 0\n",
    "        dp = [0] * n\n",
    "        cnt = [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            dp[i] = 1\n",
    "            cnt[i] = 1\n",
    "            for j in range(i):\n",
    "                if x > nums[j]:\n",
    "                    if dp[j] + 1 > dp[i]:\n",
    "                        dp[i] = dp[j] + 1\n",
    "                        cnt[i] = cnt[j]  # 重置计数\n",
    "                    elif dp[j] + 1 == dp[i]:\n",
    "                        cnt[i] += cnt[j]\n",
    "            if dp[i] > max_len:\n",
    "                max_len = dp[i]\n",
    "                ans = cnt[i]  # 重置计数\n",
    "            elif dp[i] == max_len:\n",
    "                ans += cnt[i]\n",
    "        return ans\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/number-of-longest-increasing-subsequence/solutions/1007075/zui-chang-di-zeng-zi-xu-lie-de-ge-shu-by-w12f/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        dp = [1] * len(nums)\n",
    "        cnt = [1] * len(nums)\n",
    "        _max = 0\n",
    "        for i in range(0, len(nums)):\n",
    "            res = 1\n",
    "            for j in range(0, i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    if dp[j] + 1 > res:\n",
    "                        cnt[i] = cnt[j]\n",
    "                        res = dp[j] + 1\n",
    "                    elif dp[j] + 1 == res:\n",
    "                        cnt[i] += cnt[j]\n",
    "            dp[i] = res\n",
    "            if dp[i] > _max:\n",
    "                _max = dp[i]\n",
    "                ans = cnt[i]\n",
    "            elif dp[i] == _max:\n",
    "                ans += cnt[i]\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        # 先求以i为结尾的最长子序列的长度l,\n",
    "        # 然后在dp[:i]的范围找小于等于l的数量\n",
    "        n = len(nums)\n",
    "        lengths = [0] * n\n",
    "        counts = [1] * n\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i]:\n",
    "                    if lengths[j] >= lengths[i]:\n",
    "                        lengths[i] = lengths[i] + 1\n",
    "                        counts[i] = counts[j]\n",
    "                    elif lengths[j] + 1 == lengths[i]:\n",
    "                        counts[i] += counts[j]\n",
    "        longest = max(lengths)\n",
    "\n",
    "        return sum(c for i, c in enumerate(counts) if lengths[i] == longest)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        # 先求以i为结尾的最长子序列的长度l,\n",
    "        # 然后在dp[:i]的范围找小于等于l的数量\n",
    "        n = len(nums)\n",
    "        lengths = [0] * n\n",
    "        counts = [1] * n\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i]:\n",
    "                    if lengths[j] >= lengths[i]:\n",
    "                        lengths[i] = lengths[i] + 1\n",
    "                        counts[i] = counts[j]\n",
    "                    elif lengths[j] + 1 == lengths[i]:\n",
    "                        counts[i] += counts[j]\n",
    "        longest = max(lengths)\n",
    "\n",
    "        return sum(c for i, c in enumerate(counts) if lengths[i] == longest)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        if len(nums)==0:return 0\n",
    "        dp = [[1, 1] for _ in range(len(nums))]\n",
    "        max_length = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(i):\n",
    "                if nums[j]<nums[i]:\n",
    "                    if dp[j][0]+1>dp[i][0]:\n",
    "                        dp[i][0] = dp[j][0]+1\n",
    "                        dp[i][1] = dp[j][1]\n",
    "                    elif dp[j][0] + 1 == dp[i][0]:\n",
    "                        dp[i][1] += dp[j][1]\n",
    "            max_length = max(max_length, dp[i][0])\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            if dp[i][0] == max_length:\n",
    "                res += dp[i][1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        # 状态：f[i] 表示以 nums[i]为结尾的最长子序列的长度\n",
    "        # 最优子结构：f[i] = max(f[i-1]+1, 1)\n",
    "        # 推导关系：\n",
    "        # 状态转移方程：\n",
    "        # 边界：f[0] = 1\n",
    "        # 目标：max(f[i]) where 0 <= i < n\n",
    "        # 时间复杂度：O(n)\n",
    "\n",
    "        n = len(nums)\n",
    "        f = [0] * n\n",
    "        cnt = [0] * n\n",
    "\n",
    "        max_len = 1\n",
    "        for i in range(0, n) :\n",
    "            f[i] = 1\n",
    "            cnt[i] = 1\n",
    "            for j in range(0, i): # 判断合法性\n",
    "                if nums[j] < nums[i]:\n",
    "                    if f[j] + 1 > f[i]:\n",
    "                        f[i] = f[j] + 1\n",
    "                        cnt[i] = cnt[j]\n",
    "                    elif f[j] + 1 == f[i]: # 找到一段新的\n",
    "                        cnt[i] += cnt[j]             \n",
    "            max_len = max(max_len, f[i])\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(0, n):\n",
    "            if f[i] == max_len:\n",
    "                ans += cnt[i]\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        lengths = [1] * n  \n",
    "        counts = [1] * n   \n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    if lengths[j] + 1 > lengths[i]:\n",
    "                        lengths[i] = lengths[j] + 1\n",
    "                        counts[i] = counts[j]\n",
    "                    elif lengths[j] + 1 == lengths[i]:\n",
    "                        counts[i] += counts[j]\n",
    "\n",
    "        max_length = max(lengths)\n",
    "        return sum(count for length, count in zip(lengths, counts) if length == max_length)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n, max_len, ans = len(nums), 0, 0\n",
    "        dp = [0] * n\n",
    "        cnt = [0] * n\n",
    "        for i in range(n):\n",
    "            dp[i] = 1\n",
    "            cnt[i] = 1\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    if dp[j] + 1 > dp[i]:\n",
    "                        dp[i] = dp[j] + 1\n",
    "                        cnt[i] = cnt[j]\n",
    "                    elif dp[j] + 1 == dp[i]:\n",
    "                        cnt[i] += cnt[j]\n",
    "            if dp[i] > max_len:\n",
    "                max_len = dp[i]\n",
    "                ans = cnt[i]\n",
    "            elif dp[i] == max_len:\n",
    "                ans += cnt[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "\n",
    "        # dp[i] 代表 num[i]中的最长上升子序列的长度\n",
    "        # cnt[i]代表num[i]中最长上升子序列的个数\n",
    "        n, max_len = len(nums), 0\n",
    "        ans = 0\n",
    "        dp = [1] * n\n",
    "        cnt = [1] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    if dp[j] + 1 > dp[i]:\n",
    "                        dp[i] = dp[j] + 1\n",
    "                        cnt[i] = cnt[j]\n",
    "                    elif dp[j] + 1 == dp[i]:\n",
    "                        cnt[i] += cnt[j]\n",
    "                \n",
    "            if dp[i] > max_len:\n",
    "                max_len = dp[i]\n",
    "                ans = cnt[i]\n",
    "            elif dp[i] == max_len:\n",
    "                ans += cnt[i]\n",
    "            \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        # LIS: 最长递增子序列\n",
    "        # 创建一个数组dp，用于存储以每个元素结尾的最长递增序列的长度\n",
    "        dp = [1] * n\n",
    "\n",
    "        # count[i]: 以nums[i]为结尾的LIS的个数\n",
    "        count = [1] * n\n",
    "\n",
    "        # 初始化\n",
    "        maxLength = 1\n",
    "\n",
    "        # 从0开始，填充dp数组\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[i] <= nums[j]:\n",
    "                    continue\n",
    "\n",
    "                if dp[i] < dp[j] + 1:\n",
    "                    dp[i] = dp[j] + 1\n",
    "                    count[i] = count[j]\n",
    "                elif dp[i] == dp[j] + 1:\n",
    "                    count[i] += count[j]\n",
    "\n",
    "            maxLength = max(maxLength, dp[i])\n",
    "\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            if dp[i] == maxLength:\n",
    "                result += count[i]\n",
    "\n",
    "        return result\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        lengths = [1] * len(nums)\n",
    "        counts = [1] * len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i]:\n",
    "                    if lengths[j] + 1 > lengths[i]:\n",
    "                        lengths[i] = lengths[j]+1\n",
    "                        counts[i] = counts[j]\n",
    "                    elif lengths[j] + 1== lengths[i]:\n",
    "                        counts[i] += counts[j]\n",
    "        longest = max(lengths)\n",
    "        # sum(c for i, c in enumerate(counts) if lengths[i] == longest)\n",
    "        return sum(c for i,c in enumerate(counts) if lengths[i] == longest)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        dp = [1] * n\n",
    "        cnt = [1] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    if dp[j] + 1 == dp[i]:\n",
    "                        cnt[i] += cnt[j]\n",
    "                    elif dp[j] + 1 > dp[i]:\n",
    "                        dp[i] = dp[j] + 1\n",
    "                        cnt[i] = cnt[j]\n",
    "        mx = max(dp)\n",
    "        res = 0\n",
    "        # print(mx, cnt)\n",
    "        for i in range(n):\n",
    "            if dp[i] == mx:\n",
    "                res += cnt[i]\n",
    "             \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [1 for _ in range(n)]\n",
    "        cnt = [1 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i]:\n",
    "                    if dp[i] < dp[j] + 1:\n",
    "                        dp[i] = dp[j] + 1\n",
    "                        cnt[i] = cnt[j]\n",
    "                    elif dp[i] == dp[j] + 1:\n",
    "                        cnt[i] += cnt[j]\n",
    "        max_len = max(dp)\n",
    "        return sum([c for i, c in enumerate(cnt) if dp[i] == max_len])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [1] * n\n",
    "        count = [1] * n\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    if dp[i] < dp[j] + 1:\n",
    "                        count[i] = count[j]\n",
    "                        dp[i] = dp[j]+1\n",
    "                    elif dp[i] == dp[j] +1:\n",
    "                        count[i] += count[j]\n",
    "                        dp[i] = dp[j] + 1\n",
    "\n",
    "        temp = max(dp)\n",
    "\n",
    "        res = 0\n",
    "        for i, d in enumerate(dp):\n",
    "            if d == temp:\n",
    "                res += count[i]\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1: return 1\n",
    "        dp = [1] * n\n",
    "        c = [1] * n\n",
    "        max_length = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    if dp[j] + 1 > dp[i]:\n",
    "                        dp[i] = dp[j]+1\n",
    "                        c[i] = c[j]\n",
    "                    elif dp[j]+1==dp[i]:\n",
    "                        c[i] += c[j]\n",
    "            max_length = max(max_length, dp[i])\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if dp[i] == max_length:\n",
    "                res += c[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        maxlength = 1\n",
    "        dp = [1] * len(nums)\n",
    "        cnt = [0] * len(nums)\n",
    "        cnt[0] = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i]:\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "            for j in range(i):\n",
    "                if dp[j] + 1 == dp[i] and nums[j] < nums[i]:\n",
    "                    cnt[i] += cnt[j]\n",
    "            if cnt[i] == 0:\n",
    "                cnt[i] = 1\n",
    "            maxlength = max(maxlength, dp[i])\n",
    "        for i in range(len(nums)):\n",
    "            if dp[i] == maxlength:\n",
    "                count += cnt[i]\n",
    "        print(dp)\n",
    "        print(cnt)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [1] * n\n",
    "        count = [1] * n\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    \n",
    "                \n",
    "                    if dp[i] < dp[j] + 1:\n",
    "                        dp[i] = dp[j] + 1\n",
    "                        count[i] = count[j]\n",
    "                    elif dp[i] == dp[j] +1:\n",
    "                        dp[i] = dp[j]+1\n",
    "                        count[i] += count[j]\n",
    "        temp = max(dp)\n",
    "\n",
    "        res = 0\n",
    "        for i, d in enumerate(dp):\n",
    "            if d == temp:\n",
    "                res += count[i]\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        nums.append(inf)\n",
    "        n  = len(nums)\n",
    "        dp= [0]*n # length and count\n",
    "        count = [1]*n\n",
    "        for i in range(n):\n",
    "            temp = nums[i]\n",
    "            for j in range(i):\n",
    "                if nums[j]<temp:\n",
    "                    a = dp[j]\n",
    "                    b = count[j]\n",
    "                    if dp[i]-1 == a:\n",
    "                        count[i]+=b\n",
    "                    elif dp[i]-1<a:\n",
    "                        dp[i] = a+1\n",
    "                        count[i] = b\n",
    "        return count[-1]\n",
    "        \n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        def lt673(nums):\n",
    "            n=len(nums)\n",
    "            if n==1:return 1\n",
    "            lcs=[1]*n\n",
    "            ct=[1]*n\n",
    "            for i in range(1,n):\n",
    "                for j in range(i):\n",
    "                    if nums[i]>nums[j]:\n",
    "                        if lcs[j]<lcs[i]-1:continue\n",
    "                        elif lcs[j]==lcs[i]-1:ct[i]+=ct[j]\n",
    "                        else:\n",
    "                            lcs[i]=lcs[j]+1\n",
    "                            ct[i]=ct[j]\n",
    "            max_lcs=max(lcs)\n",
    "            return sum([ ct[i] if lcs[i]==max_lcs else 0 for i in range(n) ])\n",
    "        return lt673(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        memo = [(0, 1)] * (len(nums) + 1)\n",
    "        mxLISLength, count = 0, 0\n",
    "        for i, n in enumerate(nums):\n",
    "            for j in range(i + 1):\n",
    "                if j > 0 and nums[j - 1] >= n:\n",
    "                    continue\n",
    "                currL = memo[j][0] + 1\n",
    "                if currL > memo[i + 1][0]:\n",
    "                    memo[i + 1] = (currL, memo[j][1])\n",
    "                elif currL == memo[i + 1][0]:\n",
    "                    memo[i + 1] = (currL, memo[i + 1][1] + memo[j][1])\n",
    "\n",
    "            if memo[i + 1][0] > mxLISLength:\n",
    "                mxLISLength, count = memo[i + 1][0], memo[i + 1][1]\n",
    "            elif memo[i + 1][0] == mxLISLength:\n",
    "                count += memo[i + 1][1]\n",
    "\n",
    "        return count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [1] * n\n",
    "        cnt = [1] * n\n",
    "        mx = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i]:\n",
    "                    if f[i] < f[j] + 1:\n",
    "                        f[i] = f[j] + 1\n",
    "                        cnt[i] = cnt[j]\n",
    "                    elif f[i] == f[j] + 1:\n",
    "                        cnt[i] += cnt[j]\n",
    "            if mx < f[i]:\n",
    "                mx = f[i]\n",
    "                ans = cnt[i]\n",
    "            elif mx == f[i]:\n",
    "                ans += cnt[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[1,1]] + [[0,0] for _ in  range(n - 1)]\n",
    "        max_length = 1\n",
    "        res = 1\n",
    "        for i in range(1, n):\n",
    "            dp[i][0]=1\n",
    "            dp[i][1]=1\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    if dp[j][0]+1>dp[i][0]:\n",
    "                        dp[i][0]=dp[j][0]+1\n",
    "                        dp[i][1]=dp[j][1]\n",
    "                    elif dp[j][0]+1==dp[i][0]:\n",
    "                        dp[i][1]+=dp[j][1]\n",
    "\n",
    "            if dp[i][0]>max_length:\n",
    "                max_length=dp[i][0]\n",
    "                res=dp[i][1]\n",
    "            elif dp[i][0]==max_length:\n",
    "                res+=dp[i][1]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp = [[1,1]] + [[0,0] for _ in  range(n - 1)]\n",
    "        max_length =1\n",
    "        res = 1\n",
    "        for i in range(1, n):\n",
    "            dp[i][0]=1\n",
    "            dp[i][1]=1\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "\n",
    "                    if dp[j][0]+1 > dp[i][0]:\n",
    "                        dp[i][0] = dp[j][0]+1\n",
    "                        dp[i][1] = dp[j][1]\n",
    "\n",
    "                    elif dp[j][0]+1  == dp[i][0]:\n",
    "                        dp[i][1] += dp[j][1]\n",
    "\n",
    "            if dp[i][0] > max_length:\n",
    "                max_length = dp[i][0]\n",
    "                res = dp[i][1]\n",
    "            elif dp[i][0] == max_length:\n",
    "                res += dp[i][1]   \n",
    "\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryIndexedTree:\n",
    "    __slots__ = ['n', 'c', 'd']\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.c = [0] * (n + 1)\n",
    "        self.d = [0] * (n + 1)\n",
    "\n",
    "    def update(self, x, v, cnt):\n",
    "        while x <= self.n:\n",
    "            if self.c[x] < v:\n",
    "                self.c[x] = v\n",
    "                self.d[x] = cnt\n",
    "            elif self.c[x] == v:\n",
    "                self.d[x] += cnt\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        v = cnt = 0\n",
    "        while x:\n",
    "            if self.c[x] > v:\n",
    "                v = self.c[x]\n",
    "                cnt = self.d[x]\n",
    "            elif self.c[x] == v:\n",
    "                cnt += self.d[x]\n",
    "            x -= x & -x\n",
    "        return v, cnt\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        arr = sorted(set(nums))\n",
    "        m = len(arr)\n",
    "        tree = BinaryIndexedTree(m)\n",
    "        for x in nums:\n",
    "            i = bisect_left(arr, x) + 1\n",
    "            v, cnt = tree.query(i - 1)\n",
    "            tree.update(i, v + 1, max(cnt, 1))\n",
    "        return tree.query(m)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        count = [0 for i in range(len(nums))]\n",
    "        pre = [0 for i in range(len(nums))]\n",
    "        count[0] = 1\n",
    "        pre[0] = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(0, i):\n",
    "                count[i] = max(count[i], count[j]+1) if nums[i] > nums[j] else max(count[i], 1)\n",
    "            \n",
    "            for j in range(0, i):\n",
    "                if count[i] == count[j]+1 and nums[i] > nums[j]:\n",
    "                    pre[i] += pre[j]\n",
    "\n",
    "            pre[i] = max(pre[i], 1)\n",
    "        longest = max(count)\n",
    "        num = 0\n",
    "        for i in range(len(count)):\n",
    "            if count[i] == longest:\n",
    "                num += pre[i]\n",
    "        \n",
    "        # print(count)\n",
    "        # print(pre)\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        maxLen = 1;\n",
    "        n = len(nums);\n",
    "        dp = [1] * n;\n",
    "        count = [1] * n;\n",
    "        for i in range(1, n):\n",
    "            for j in range(0, i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    if dp[i] < 1+dp[j]:\n",
    "                        dp[i] = 1+dp[j];\n",
    "                        count[i] = count[j];\n",
    "                        maxLen = max(maxLen, dp[i]);\n",
    "                    elif dp[i] == 1+dp[j]:\n",
    "                        count[i] += count[j];\n",
    "        result = 0;\n",
    "        for i in range(0, n):\n",
    "            if dp[i] == maxLen:\n",
    "                result += count[i];\n",
    "        return result;\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        if m <= 1:\n",
    "            return m\n",
    "\n",
    "        dp = [1] * m\n",
    "        count = [1] * m\n",
    "\n",
    "        max_count = 0\n",
    "        for i, num1 in enumerate(nums):\n",
    "            for j, num2 in enumerate(nums[:i]):\n",
    "                if num1 > num2:\n",
    "                    if dp[i] < dp[j] + 1:\n",
    "                        count[i] = count[j]\n",
    "                        dp[i] = dp[j] + 1\n",
    "                    elif dp[i] == dp[j] + 1:\n",
    "                        count[i] += count[j]\n",
    "                    \n",
    "                if dp[i] > max_count:\n",
    "                    max_count = dp[i]\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            if max_count == dp[i]:\n",
    "                res += count[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "* 跟最长递增子序列类似，不过需要统计两个变量，dp[0]表示最长递增子序列的长度，dp[1]表示最长递增子序列的个数，递推公式如下：\n",
    "   * 如果nums[i]>nums[j]:\n",
    "     * 如果在[0, i-1]的范围内，找到了j，使得dp[j][0] + 1 > dp[i][0]，说明找到了一个更长的递增子序列，那么以j为结尾的子串的最长递增子序列的个数，就是最新的以i为结尾的子串的最长递增子序列的个数，即：dp[i][1] = dp[j][1]，且最大长度更新为dp[j][0]+1\n",
    "     * 如果在[0, i-1]的范围内，找到了j，使得dp[j][0] + 1 == dp[i][0]，说明找到了两个相同长度的递增子序列。那么以i为结尾的子串的最长递增子序列的个数就应该加上以j为结尾的子串的最长递增子序列的个数，即：dp[i][1] += dp[j][1];\n",
    "     * 同时还需要记录最大子序列长度的数值 max_num，用于最后的输出。\n",
    "'''\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        dp = [[1,1] for i in range(len(nums))]\n",
    "        max_num = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(i):\n",
    "                if nums[i]>nums[j]:\n",
    "                    if dp[j][0]+1>dp[i][0]:\n",
    "                        dp[i][0] = dp[j][0]+1\n",
    "                        dp[i][1] = dp[j][1]\n",
    "                        max_num = max(max_num, dp[i][0])\n",
    "                    elif dp[j][0]+1==dp[i][0]:\n",
    "                        dp[i][1]+=dp[j][1]\n",
    "\n",
    "        res = 0\n",
    "        for cur_dp in dp:\n",
    "            if cur_dp[0]==max_num:\n",
    "                res += cur_dp[1]\n",
    "        return res\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        nums.append(inf)\n",
    "        n  = len(nums)\n",
    "        dp= [[0,1]]*n # length and count\n",
    "        for i in range(n):\n",
    "            temp = nums[i]\n",
    "            for j in range(i):\n",
    "                if nums[j]<temp:\n",
    "                    # \n",
    "                    if dp[i][0]-1 == dp[j][0]:\n",
    "                        dp[i][1]+=dp[j][1]\n",
    "                    elif dp[i][0]-1<dp[j][0]:\n",
    "                        dp[i] = [dp[j][0]+1,dp[j][1]]\n",
    "        return dp[-1][1]\n",
    "        \n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        l=len(nums)\n",
    "        dp=[1]*l\n",
    "        cnt=[0]*l\n",
    "        cnt[0]=1\n",
    "        for i in range(1,l):\n",
    "            for j in range(i):\n",
    "                if nums[i]>nums[j]:\n",
    "                    dp[i]=max(dp[i],dp[j]+1)\n",
    "        for i in range(1,l):\n",
    "            for j in range(i):\n",
    "                if nums[i]>nums[j] and dp[i]==dp[j]+1:\n",
    "                    cnt[i]+=cnt[j]\n",
    "                if dp[i]==1:\n",
    "                    cnt[i]=1\n",
    "        #for i in range(l):\n",
    "            #if cnt[i]==0:\n",
    "                #cnt[i]+=1            \n",
    "                    \n",
    "        print(cnt)\n",
    "        print(dp)\n",
    "        m=max(dp)\n",
    "        res=0\n",
    "        for i in range(l):\n",
    "            if dp[i]==m:\n",
    "                res+=cnt[i]\n",
    "        return res   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        dp = [[1,1] for i in range(len(nums))]\n",
    "        max_num = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(i):\n",
    "                if nums[i]>nums[j]:\n",
    "                    if dp[j][0]+1>dp[i][0]:\n",
    "                        dp[i][0] = dp[j][0]+1\n",
    "                        dp[i][1] = dp[j][1]\n",
    "                        max_num = max(max_num, dp[i][0])\n",
    "                    elif dp[j][0]+1==dp[i][0]:\n",
    "                        dp[i][1]+=dp[j][1]\n",
    "\n",
    "        res = 0\n",
    "        for cur_dp in dp:\n",
    "            if cur_dp[0]==max_num:\n",
    "                res += cur_dp[1]\n",
    "        return res\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        g = []\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        dp = [1] *n\n",
    "        counter = [1] * n\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i]:\n",
    "                    if dp[i] < dp[j] + 1:\n",
    "                        dp[i] = dp[j] + 1\n",
    "                        counter[i] = counter[j]\n",
    "                    elif dp[i] == dp[j] + 1:\n",
    "                        counter[i] = counter[i] + counter[j]  \n",
    "        print(dp)\n",
    "        print(counter)\n",
    "        return sum([counter[i] for i in range(n) if dp[i] == max(dp)])\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp = [[0,0] for _ in  range(n )]\n",
    "        max_length =0\n",
    "        res = 0\n",
    "        for i in range( n):\n",
    "            dp[i][0]=1\n",
    "            dp[i][1]=1\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "\n",
    "                    if dp[j][0]+1 > dp[i][0]:\n",
    "                        dp[i][0] = dp[j][0]+1\n",
    "                        dp[i][1] = dp[j][1]\n",
    "\n",
    "                    elif dp[j][0]+1  == dp[i][0]:\n",
    "                        dp[i][1] += dp[j][1]\n",
    "\n",
    "            if dp[i][0] > max_length:\n",
    "                max_length = dp[i][0]\n",
    "                res = dp[i][1]\n",
    "            elif dp[i][0] == max_length:\n",
    "                res += dp[i][1]   \n",
    "\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "\n",
    "        # Solution: Dynamic Programming\n",
    "        n = len(nums)\n",
    "\n",
    "        dp = [[1, 1] for _ in range(n)]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                \n",
    "                if nums[i] > nums[j]:\n",
    "        \n",
    "                    if dp[j][0] + 1 > dp[i][0]:\n",
    "                        dp[i][0] = dp[j][0] + 1\n",
    "                        dp[i][1] = dp[j][1]\n",
    "                    \n",
    "                    elif dp[j][0] + 1 == dp[i][0]:\n",
    "                        dp[i][1] += dp[j][1]\n",
    "\n",
    "        \n",
    "        max_length = 0\n",
    "        cnt = 0\n",
    "\n",
    "        for d in dp:\n",
    "\n",
    "            if d[0] > max_length:\n",
    "\n",
    "                cnt = d[1]\n",
    "                max_length = d[0]\n",
    "            \n",
    "            elif d[0] == max_length:\n",
    "                cnt += d[1]\n",
    "\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [1]*n\n",
    "        for i in range(n):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if (nums[j] < nums[i]):\n",
    "                    dp[i] = max(dp[i], dp[j]+1)\n",
    "        return max(dp)\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[1, 0] for _ in range(n)]\n",
    "        print(dp)\n",
    "        dp[0][1] = 1\n",
    "        print(dp)\n",
    "        for i in range(n):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if (nums[j] < nums[i]):\n",
    "                    dp[i][0] = max(dp[i][0], dp[j][0]+1)\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if (nums[j] < nums[i] and dp[i][0] == dp[j][0] + 1):\n",
    "                    dp[i][1] = dp[i][1] + dp[j][1]\n",
    "            if dp[i][1] == 0:\n",
    "                dp[i][1] = 1\n",
    "        m = max(dp[i][0] for i in range(n))\n",
    "        ans = 0\n",
    "        print(dp, m)\n",
    "        for i in range(n):\n",
    "            if dp[i][0] == m:\n",
    "                ans = ans + dp[i][1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[1,1] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            acc = 1\n",
    "            for j in range(i):\n",
    "                if nums[i]>nums[j]:\n",
    "                    if dp[j][0]+1>dp[i][0]:\n",
    "                        acc = dp[j][1]\n",
    "                        dp[i][0] = dp[j][0]+1\n",
    "                    elif dp[j][0]+1==dp[i][0]:\n",
    "                        acc+=dp[j][1]\n",
    "            dp[i][1] = acc\n",
    "        print(dp)\n",
    "        dp.sort(key=lambda x:-x[0])\n",
    "        res = 0\n",
    "        tmp = dp[0][0]\n",
    "        if tmp==1:return n\n",
    "        for c in dp:\n",
    "            if c[0]==tmp:\n",
    "                res+=c[1]\n",
    "            else:break\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[[1 for _ in range(2)]for _ in range(n)]\n",
    "        ans=1\n",
    "        rem=[]\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[i]>nums[j]:\n",
    "                    if dp[j][0]+1>dp[i][0]:\n",
    "                        dp[i][0]=dp[j][0]+1\n",
    "                        dp[i][1]=dp[j][1]\n",
    "                    elif dp[j][0]+1==dp[i][0]:\n",
    "                        dp[i][1]+=dp[j][1]\n",
    "            if dp[i][0]==ans:\n",
    "                rem.append(i)\n",
    "            if dp[i][0]>ans:\n",
    "                ans=dp[i][0]\n",
    "                rem=[i]\n",
    "                \n",
    "        #print(rem,dp)\n",
    "        if  ans==1:\n",
    "            return n\n",
    "        else:\n",
    "            ret=0\n",
    "            for i in rem:\n",
    "                ret+=dp[i][1]\n",
    "            return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        dp = []\n",
    "        tree = collections.defaultdict(list)\n",
    "        for i in nums:\n",
    "            idx = bisect.bisect_left(dp,i)\n",
    "            if idx == len(dp):\n",
    "                dp.append(i)\n",
    "            else:\n",
    "                dp[idx] = i\n",
    "            total = 0\n",
    "            for counter, last_num in tree[idx]:\n",
    "                if last_num < i:\n",
    "                    total += counter\n",
    "            tree[idx+1].append((max(1,total), i))\n",
    "        return sum(i[0] for i in tree[len(tree)-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        dp = []\n",
    "        records = defaultdict(list)\n",
    "        records[0] = [(-inf, 1)]\n",
    "        for num in nums:\n",
    "            idx = bisect_left(dp, num)\n",
    "            if idx < len(dp):\n",
    "                dp[idx] = num\n",
    "            else:\n",
    "                dp.append(num)\n",
    "            records[idx + 1].append((num, sum(v for k,v in records[idx] if k < num)))\n",
    "        return sum(v[1] for v in records[max(records.keys())])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        def binarySearch(n,f):\n",
    "            l,r = 0,n-1\n",
    "            while l<=r:\n",
    "                mid = (l+r)>>1\n",
    "                if f(mid):\n",
    "                    l = mid+1\n",
    "                else:\n",
    "                    r = mid-1\n",
    "            return l\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [] # dp[i] is all element could be length i \n",
    "        cnt = [] # use prefix sum to count the number of such length \n",
    "        # cnt[i][j] is the number of sequence ended with dp[i][j] \n",
    "\n",
    "        for n in nums:\n",
    "            # binary search the lowest number with the length \n",
    "            i  = binarySearch(len(dp),lambda i: dp[i][-1]<n)\n",
    "            # k is the longest length such that n >\n",
    "\n",
    "            \n",
    "            count = 1\n",
    "            if i>0:\n",
    "                k = binarySearch(len(dp[i-1]),lambda p: dp[i-1][p] >= n )\n",
    "                count = cnt[i-1][-1] - cnt[i-1][k]\n",
    "\n",
    "\n",
    "            if i == len(dp):\n",
    "                dp.append([n])\n",
    "                cnt.append([0,count])\n",
    "            else:\n",
    "                dp[i].append(n)\n",
    "                cnt[i].append(cnt[i][-1]+count)\n",
    "            # 二分 每一列最后一位 > 的位置\n",
    "            # 二分 前一列 加起来 用prefix sum\n",
    "\n",
    "        return cnt[-1][-1]\n",
    "            \n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        # dp[i]表示是一个长度为2的列表，\n",
    "        # dp[i][0]表示以i为结尾的最长子序列的长度，默认为1（nums[i]自己）\n",
    "        # dp[i][1]表示以i为结尾的最长子序列的个数\n",
    "        dp = [[1,1] for _ in range(len(nums))]\n",
    "        for i in range(1, len(nums)):\n",
    "            temp_list = [dp[j] for j in range(0, i) if nums[i] > nums[j]]\n",
    "            if len(temp_list) != 0:\n",
    "                max_dp = max(temp_list)[0]\n",
    "                dp[i] = [max_dp+1 , sum(item[1] for item in temp_list if item[0] == max_dp)]\n",
    "        max_dp = max(dp)[0]\n",
    "        return sum(item[1] for item in dp if item[0] == max_dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [[0]*2 for _ in range(n)]\n",
    "    \n",
    "    def query(self, i):\n",
    "        f = g = 0\n",
    "        while i>0:\n",
    "            fi, gi = self.tree[i]\n",
    "            if f == fi:\n",
    "                g += gi\n",
    "            elif f<fi:\n",
    "                f = fi\n",
    "                g = gi\n",
    "            i -= i&-i\n",
    "        return f, g\n",
    "\n",
    "    def add(self, i, f, g):\n",
    "        while i<len(self.tree):\n",
    "            fi, gi = self.tree[i]\n",
    "            if fi == f:\n",
    "                gi += g\n",
    "            elif fi<f:\n",
    "                fi = f\n",
    "                gi = g\n",
    "            self.tree[i] = [fi, gi]\n",
    "            i += i&-i\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        tree = [[0] * 2 for _ in range(n + 1)]\n",
    "        def query(i):\n",
    "            f = g = 0\n",
    "            while i > 0:\n",
    "                fi, gi = tree[i]\n",
    "                if fi > f:\n",
    "                    f = fi\n",
    "                    g = gi\n",
    "                elif fi == f:\n",
    "                    g += gi\n",
    "                i -= i & -i\n",
    "            return f, g\n",
    "        def update(i, f, g):\n",
    "            while i < len(tree):\n",
    "                fi, gi = tree[i]\n",
    "                if fi < f:\n",
    "                    fi = f\n",
    "                    gi = g\n",
    "                elif fi == f:\n",
    "                    gi += g\n",
    "                tree[i] = fi, gi\n",
    "                i += i & -i\n",
    "        # 树状数组下标代表值域，从左往右添加\n",
    "        mp = {x: i + 1 for i, x in enumerate(sorted(set(nums)))}\n",
    "        for x in nums:\n",
    "            i = mp[x]\n",
    "            fi, gi = query(i - 1)\n",
    "            update(i, fi + 1, max(1, gi))\n",
    "        return query(n)[1]\n",
    "\n",
    "        # 树状数组下标和数组下标一致，值从小到大添加\n",
    "        # ids = sorted(range(n), key=lambda i: (nums[i], -i))\n",
    "        # for i in ids:\n",
    "        #     fi, gi = query(i)\n",
    "        #     update(i + 1, fi + 1, max(1, gi))\n",
    "        #return query(n)[1]\n",
    "\n",
    "        # n = len(nums)\n",
    "        # ids = sorted(range(n), key=lambda i: (nums[i], -i))\n",
    "        # tree = BIT(n+1)\n",
    "        # for i in ids:\n",
    "        #     f, g = tree.query(i)\n",
    "        #     tree.add(i+1, f+1, max(1, g))\n",
    "        # return tree.query(n)[1]\n",
    "\n",
    "#         #f[i]:以nums[i]结尾的最长递增子序列长度\n",
    "#         #g[i]:以nums[i]结尾的最长递增子序列个数\n",
    "#         n = len(nums)\n",
    "#         f, g = [1]*n, [1]*n\n",
    "#         res = max_len = 0\n",
    "#         for i, x in enumerate(nums):\n",
    "#             for j in range(i):\n",
    "#                 if x>nums[j]:\n",
    "#                     if f[i] == f[j]+1:\n",
    "#                         g[i] += g[j]\n",
    "#                     elif f[i]<f[j]+1:\n",
    "#                         f[i] = f[j]+1\n",
    "#                         g[i] = g[j]\n",
    "#             if f[i] == max_len:\n",
    "#                 res += g[i]\n",
    "#             elif f[i]>max_len:\n",
    "#                 max_len = f[i]\n",
    "#                 res = g[i]\n",
    "#         return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findNumberOfLIS(self, nums):\n",
    "        import bisect\n",
    "        dp = []\n",
    "        tree = collections.defaultdict(list)\n",
    "        for i in nums:\n",
    "            idx = bisect.bisect_left(dp,i)\n",
    "            if idx == len(dp):\n",
    "                dp.append(i)\n",
    "            else:\n",
    "                dp[idx] = i\n",
    "            total = 0\n",
    "            for counter, last_num in tree[idx]:\n",
    "                if last_num < i:\n",
    "                    total += counter\n",
    "            tree[idx+1].append((max(1,total), i))\n",
    "        return sum(i[0] for i in tree[len(tree)-1])\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        # if not nums: return 0\n",
    "        # l = len(nums)\n",
    "        # dq = list()\n",
    "        # totals = list()\n",
    "        # for num in nums:\n",
    "        #     index = len(dq)-1\n",
    "        #     if not dq or num > dq[-1]:\n",
    "        #         dq.append(num)\n",
    "        #         totals.append(defaultdict(int))\n",
    "        #     else:\n",
    "        #         while index >= 0 and dq[index] >= num:\n",
    "        #             index -= 1\n",
    "        #         dq[index+1] = num\n",
    "        #     if not index+1:\n",
    "        #         totals[index+1][num] +=1\n",
    "        #     else:\n",
    "        #         totals[index+1][num] += sum([val for key,val in totals[index].items() if key < num])\n",
    "        # return sum(totals[-1].values())\n",
    "\n",
    "\n",
    "\n",
    "        dp, count = [], []\n",
    "        for num in nums:\n",
    "            l, r = 0, len(dp)\n",
    "            while l < r:\n",
    "                mid = (l + r) >> 1\n",
    "                if dp[mid][-1] >= num:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            i = l\n",
    "            c = 1\n",
    "            if i > 0:\n",
    "                # 找d[i-1]中结尾小于num的数量\n",
    "                l, r = 0, len(dp[i - 1])\n",
    "                while l < r:\n",
    "                    mid = (l + r) >> 1\n",
    "                    if dp[i-1][mid] < num:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                k = l\n",
    "                c = count[i-1][-1] - count[i-1][k]\n",
    "            if i == len(dp):\n",
    "                dp.append([num])\n",
    "                count.append([0, c])\n",
    "            else:\n",
    "                dp[i].append(num)\n",
    "                count[i].append(c + count[i][-1])\n",
    "        return count[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        # 获取最大maxlen及其cnt\n",
    "        def getMax(val1, val2):\n",
    "            res = []\n",
    "            # maxlen相同，则该maxlen的cnt相加\n",
    "            if val1[0] == val2[0]:\n",
    "                res = [val1[0], val1[1] + val2[1]]\n",
    "            else:\n",
    "                res = val2.copy() if val1[0] < val2[0] else val1.copy()\n",
    "            return res\n",
    "\n",
    "        class NumTree:\n",
    "            def __init__(self, n):\n",
    "                # [maxlen, cnt]\n",
    "                self.nums = [[0, 0] for _ in range(n + 1)]\n",
    "\n",
    "            # 分区间求去最大maxlen及其cnt值\n",
    "            def get(self, idx):\n",
    "                res = [0, 0]\n",
    "                while idx:\n",
    "                    res = getMax(self.nums[idx], res)\n",
    "                    idx -= idx & (-idx)\n",
    "                return res\n",
    "\n",
    "            # 更新所有包含该值的区间的maxlen及其cnt值\n",
    "            def update(self, idx, val):\n",
    "                while idx < len(self.nums):\n",
    "                    self.nums[idx] = getMax(self.nums[idx], val)\n",
    "                    idx += idx & (-idx)\n",
    "\n",
    "        n = len(nums)\n",
    "        # 数组序列化\n",
    "        sortmap = dict(zip(sorted(set(nums)), range(1, n + 1)))\n",
    "        seqtree = NumTree(len(sortmap))\n",
    "        ans = [0, 0]\n",
    "        for i in range(n):\n",
    "            idx = sortmap[nums[i]]\n",
    "            newmax = [i + j for i, j in zip(seqtree.get(idx - 1), [1, 0])]\n",
    "            if newmax[1] == 0:\n",
    "                newmax[1] = 1\n",
    "            seqtree.update(idx, newmax)\n",
    "            ans = getMax(ans, newmax)\n",
    "        return ans[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        mp = dict()\n",
    "        for i, x in enumerate(sorted(set(nums))):\n",
    "            mp[x] = i + 1\n",
    "        b = BIT(len(mp))\n",
    "        print(mp)\n",
    "        for x in nums:\n",
    "            idx = mp[x]\n",
    "            le, cnt = b.find(idx-1)\n",
    "            b.update(idx, (le + 1, max(cnt, 1)))\n",
    "        return b.find(len(mp))[1]\n",
    "\n",
    "\n",
    "class BIT:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.tree = [(0, 0)] * (n + 1)\n",
    "        self.n = n + 1\n",
    "\n",
    "    def update(self, i, item):\n",
    "        while i < self.n:\n",
    "            le, cnt = self.tree[i]\n",
    "            if le == item[0]:\n",
    "                cnt += item[1]\n",
    "            elif le < item[0]:\n",
    "                le, cnt = item\n",
    "            self.tree[i] = le, cnt\n",
    "            i += i & -i\n",
    "\n",
    "\n",
    "    def find(self, i):\n",
    "        le, cnt = 0, 0\n",
    "        while i > 0:\n",
    "            if le == self.tree[i][0]:\n",
    "                cnt += self.tree[i][1]\n",
    "            elif le < self.tree[i][0]:\n",
    "                le = self.tree[i][0]\n",
    "                cnt =self.tree[i][1]\n",
    "            i -= i & -i\n",
    "        return le, cnt\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        mono = [nums[0]]\n",
    "        dp = defaultdict(lambda: defaultdict(int))\n",
    "        for num in nums:\n",
    "            if num > mono[-1]:\n",
    "                length = len(mono)\n",
    "                mono.append(num)\n",
    "            else:\n",
    "                length = bisect.bisect_left(mono, num)\n",
    "                mono[length] = num\n",
    "            if length == 0:\n",
    "                dp[0][num] += 1\n",
    "            else:\n",
    "                d = dp[length]\n",
    "                prev_d = dp[length-1]\n",
    "                to_del = []\n",
    "                for val, cnt in prev_d.items():\n",
    "                    if val >= num:\n",
    "                        to_del.append(val)\n",
    "                    else:\n",
    "                        d[num] += cnt\n",
    "                for val in to_del:\n",
    "                    prev_d.pop(val)\n",
    "        return sum(dp[max(dp)].values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findNumberOfLIS(self, nums):\n",
    "        #在#300的基础之上，做一个dict 保存必要的关键信息，如长度，路径数量，结尾的值\n",
    "        import bisect\n",
    "        dp = []\n",
    "        tree = collections.defaultdict(list)\n",
    "        for i in nums:\n",
    "            # print(\"i is\", i)\n",
    "            idx = bisect.bisect_left(dp,i)\n",
    "            # print(\"idx is\",idx)\n",
    "            # print(\"len(dp) is\",len(dp))\n",
    "            # print(\"dp is\",dp)\n",
    "            if idx == len(dp):\n",
    "                dp.append(i)\n",
    "            else:\n",
    "                dp[idx] = i\n",
    "            total = 0\n",
    "            # print(\"total is\",total)\n",
    "            for counter, last_num in tree[idx]:\n",
    "                if last_num < i:\n",
    "                    total += counter\n",
    "                    # print(\"total is\",total)\n",
    "                    # print(\"counter is\",counter,\"last_num is\",last_num)\n",
    "            tree[idx+1].append((max(1,total), i))\n",
    "            # print(tree)\n",
    "        return sum(i[0] for i in tree[len(tree)-1])\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums): # nums:List[int], rtype:int\n",
    "        inf_ = -65536\n",
    "        for _ in range(10):\n",
    "            inf_ *= 2\n",
    "        dp, count, length = [inf_], [{-1:1}], 0\n",
    "        # count[i]  是 LIS长度为i 的情况 [{末元素索引:路径个数}] - {ix:树深度}\n",
    "        # dp[ix_dp] 是 LIS长度ix_dp下 尽可能小LIS的末元素\n",
    "        for i, ei in enumerate(nums):\n",
    "            if ei > dp[-1]: # 成为最长\n",
    "                count.append({})\n",
    "                # print(count)\n",
    "                dp.append(ei)\n",
    "                length += 1\n",
    "                count[length][i] = 0\n",
    "                for key, val in count[length-1].items():\n",
    "                    if key == -1 or nums[key] < ei:\n",
    "                        count[length][i] += val\n",
    "            elif ei <= dp[-1]:\n",
    "                ix_dp = bs_ix_left(dp, ei)\n",
    "                dp[ix_dp] = ei\n",
    "                if count[ix_dp].get(i) is None:\n",
    "                    count[ix_dp][i] = 0\n",
    "                for key, val in count[ix_dp-1].items():\n",
    "                    if key == -1 or nums[key] < ei:\n",
    "                        count[ix_dp][i] += val\n",
    "                # count[i] += 1\n",
    "                # dp[] = ei\n",
    "        # print(dp)\n",
    "        # print(count)\n",
    "        return sum(count[-1].values())\n",
    "def bs_ix_left(nums, target):\n",
    "    if len(nums) and nums[-1] < target:\n",
    "        return len(nums)\n",
    "    ix_l, ix_r = 0, len(nums) - 1\n",
    "    while ix_l < ix_r:  # [,] - 是否会卡住与开闭区间无关, 关键在于 mid 选 mid_l 还是 mid_r\n",
    "        mid = ix_l + (ix_r - ix_l) // 2  # mid_l\n",
    "        if nums[mid] < target:\n",
    "            ix_l = mid + 1  # ix_l 保持选中\n",
    "        else:  # mid_l属于目标区间移动右 - 最终可闭合\n",
    "            ix_r = mid  # 不选中 mid\n",
    "    return ix_l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        dp = collections.defaultdict(collections.Counter)\n",
    "        dp[-1][float('-inf')] = 1\n",
    "        seq = []\n",
    "        for num in nums:\n",
    "            idx = bisect.bisect_left(seq, num)\n",
    "            if idx == len(seq):\n",
    "                seq.append(num)\n",
    "            else:\n",
    "                seq[idx] = num\n",
    "            dp[idx][num] += sum([dp[idx-1][val] for val in dp[idx-1] if val < num])\n",
    "        return sum(dp[len(seq)-1].values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        dp = [[1,1]] * len(nums)\n",
    "        res_dic = collections.defaultdict(int)\n",
    "        res_dic[1] = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            dic = collections.defaultdict(int)\n",
    "            dic[1] = 1\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    dic[dp[j][0]+1] += dp[j][1]\n",
    "            v, c = sorted(dic.items(), key=lambda x: x[0], reverse=True)[0]\n",
    "            dp[i] = [v, c]\n",
    "            res_dic[v] += c\n",
    "        \n",
    "        v, c = sorted(res_dic.items(), key=lambda x: x[0], reverse=True)[0]\n",
    "        return c\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        dp = [[1,1] for _ in range(len(nums))]\n",
    "        for i in range(1,len(nums)):\n",
    "            l = []\n",
    "            for j in range(i,-1,-1):\n",
    "                if nums[j] < nums[i]:\n",
    "                    l.append(dp[j])\n",
    "            m = 0\n",
    "            for k in l:\n",
    "                m = max(k[0],m)\n",
    "            l_ = [[x,y] for x,y in l if x == m]\n",
    "            dp[i][0] = m+1\n",
    "            dp[i][1] = max(sum([y for _,y in l_]),1)\n",
    "            \n",
    "        d = sorted(dp,key=lambda x:x[0])\n",
    "        return sum([y for _,y in d if _ == d[-1][0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = {} # key = index, value =[length of LIS, count]\n",
    "        lenLIS, res = 0, 0 #length of LIS, count of LIS\n",
    "\n",
    "        #i = start of subseq\n",
    "        for i in range(n-1,-1,-1):\n",
    "            maxLen, maxCnt = 1, 1 #len, cnt of LIS starting from i\n",
    "\n",
    "            for j in range(i + 1, n): \n",
    "                if nums[j] > nums[i]:\n",
    "                    length, count = dp[j]\n",
    "                    if length + 1 > maxLen:\n",
    "                        maxLen, maxCnt = length + 1, count\n",
    "                    elif length + 1 == maxLen:\n",
    "                        maxCnt += count\n",
    "\n",
    "            if maxLen > lenLIS:\n",
    "                lenLIS, res = maxLen, maxCnt\n",
    "            elif maxLen == lenLIS:\n",
    "                res += maxCnt\n",
    "            print(maxLen, lenLIS, res)\n",
    "            dp[i] = [maxLen, maxCnt]\n",
    "\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        dp = collections.defaultdict(collections.Counter)\n",
    "        dp[-1][float('-inf')] = 1\n",
    "        seq = []\n",
    "        for num in nums:\n",
    "            idx = bisect.bisect_left(seq, num)\n",
    "            if idx == len(seq):\n",
    "                seq.append(num)\n",
    "            else:\n",
    "                seq[idx] = num\n",
    "            dp[idx][num] += sum([dp[idx-1][val] for val in dp[idx-1] if val < num])\n",
    "        return sum(dp[len(seq)-1].values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        def pushUp(root):\n",
    "            if tree[2*root][0]> tree[2*root+1][0]:\n",
    "                tree[root]= tree[2*root].copy()\n",
    "            elif tree[2*root][0]< tree[2*root+1][0]:\n",
    "                tree[root]= tree[2*root+1].copy()\n",
    "            else:\n",
    "                tree[root][0]= tree[2*root][0]\n",
    "                tree[root][1] = tree[2*root][1]+tree[2*root+1][1] #根据儿子，更新父节点信息\n",
    "\n",
    "        def update(L, val,val1, left, right, root):\n",
    "            if left == right:\n",
    "                #print(left,root,val)\n",
    "                if tree[root][0]<val:\n",
    "                    tree[root][0] = val\n",
    "                    tree[root][1] = val1\n",
    "                elif tree[root][0] == val:\n",
    "\n",
    "                    tree[root][1] += val1\n",
    "                return\n",
    "            mid = left + (right-left) // 2\n",
    "            if L <= mid: #左子树统统更新；\n",
    "                update(L, val, val1,left, mid, 2*root)\n",
    "            else:\n",
    "                update(L, val, val1,mid+1, right, 2*root+1)\n",
    "\n",
    "            pushUp(root) #最后更新root对应值\n",
    "        \n",
    "        def query(L, R, left, right, root):\n",
    "            #print(L,R,left,right)\n",
    "            if R < left or L > right:\n",
    "                return [0,0]\n",
    "            if L <= left and right <= R: #如果在已有区间之外，返回已有区间结果\n",
    "                return tree[root]\n",
    "            #现在L>left 或R <right;\n",
    "            mid = left + (right-left) // 2 #否则和已有区间有重合；或在内部\n",
    "            ans = [0,0]\n",
    "            if L <= mid: # L在mid的左边，更新右边即可\n",
    "                a,b = query(L, R, left, mid, 2*root)\n",
    "                if a >ans[0]:\n",
    "                    ans = [a,b]\n",
    "                elif a ==ans[0]:\n",
    "                    ans[1]+=b\n",
    "            if R > mid:\n",
    "                a,b =query(L, R, mid+1, right, 2*root+1)\n",
    "                if a >ans[0]:\n",
    "                    ans = [a,b]\n",
    "                elif a ==ans[0]:\n",
    "                    ans[1]+=b\n",
    "            return ans\n",
    "        uniques = set(nums)\n",
    "        mapd = {v:i+1 for i,v in enumerate(sorted(uniques))}\n",
    "        print(mapd)\n",
    "        l = 1\n",
    "        r = len(mapd)\n",
    "        tree = [[0,0] for _ in range(4*(r-l+1))]\n",
    "        #print('aaa',l,r)\n",
    "        for i,v in enumerate(nums):\n",
    "            r1 = 1 #最小值\n",
    "            r2 = mapd[v]\n",
    "            a = query(l, r2-1, l,r, 1)\n",
    "            #print('result',r2,a[0]+1,max(a[1],1))\n",
    "            update(r2,a[0]+1,max(a[1],1),l,r,1)\n",
    "            #print(tree)\n",
    "        return tree[1][1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        dp = collections.defaultdict(collections.Counter)\n",
    "        dp[-1][float('-inf')] = 1\n",
    "        seq = []\n",
    "        for num in nums:\n",
    "            idx = bisect.bisect_left(seq, num)\n",
    "            if idx == len(seq):\n",
    "                seq.append(num)\n",
    "            else:\n",
    "                seq[idx] = num\n",
    "            dp[idx][num] += sum([dp[idx-1][val] for val in dp[idx-1] if val < num])\n",
    "        return sum(dp[len(seq)-1].values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        dp = collections.defaultdict(collections.Counter)\n",
    "        dp[-1][float('-inf')] = 1\n",
    "        seq = []\n",
    "        for num in nums:\n",
    "            idx = bisect.bisect_left(seq, num)\n",
    "            if idx == len(seq):\n",
    "                seq.append(num)\n",
    "            else:\n",
    "                seq[idx] = num\n",
    "            dp[idx][num] += sum([dp[idx-1][val] for val in dp[idx-1] if val < num])\n",
    "        return sum(dp[len(seq)-1].values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 线段树的节点类\n",
    "class Node:\n",
    "    def __init__(self, val=[0, 1]):\n",
    "        self.left = -1                              # 区间左边界\n",
    "        self.right = -1                             # 区间右边界\n",
    "        self.val = val    \n",
    "\n",
    "\n",
    "\n",
    "def build(tree, index, left, right):\n",
    "    tree[index].left = left\n",
    "    tree[index].right = right\n",
    "    if left == right:                           # 叶子节点，节点值为对应位置的元素值\n",
    "        tree[index].val = [0, 0]\n",
    "        return\n",
    "\n",
    "    mid = left + (right - left) // 2            # 左右节点划分点\n",
    "    left_index = index * 2 + 1                  # 左子节点的存储下标\n",
    "    right_index = index * 2 + 2                 # 右子节点的存储下标\n",
    "    build(tree, left_index, left, mid)         # 递归创建左子树\n",
    "    build(tree, right_index, mid + 1, right)   # 递归创建右子树\n",
    "\n",
    "    tree[index].val = merge(\n",
    "        tree[left_index].val, tree[right_index].val)   # 向上更新节点的区间值\n",
    "\n",
    "    # 单点更新实现方法：将 nums[i] 更改为 val，节点的存储下标为 index\n",
    "def update_point(tree, i, val, index):\n",
    "    left = tree[index].left\n",
    "    right = tree[index].right\n",
    "\n",
    "    if left == i and right == i:\n",
    "        tree[index].val = merge(tree[index].val, val)\n",
    "        return\n",
    "\n",
    "    mid = left + (right - left) // 2   # 左右节点划分点\n",
    "    left_index = index * 2 + 1         # 左子节点的存储下标\n",
    "    right_index = index * 2 + 2        # 右子节点的存储下标\n",
    "    if i <= mid:                       # 在左子树中更新节点值\n",
    "        update_point(tree, i, val, left_index)\n",
    "    else:                              # 在右子树中更新节点值\n",
    "        update_point(tree, i, val, right_index)\n",
    "\n",
    "    tree[index].val = merge(\n",
    "        tree[left_index].val, tree[right_index].val)   # 向上更新节点的区间值\n",
    "\n",
    "    # 区间查询实现方法：在线段树中搜索区间为 [q_left, q_right] 的区间值\n",
    "\n",
    "def query_interval(tree, q_left, q_right, index):\n",
    "    left = tree[index].left\n",
    "    right = tree[index].right\n",
    "\n",
    "    # 节点所在区间被 [q_left, q_right] 所覆盖\n",
    "    if left >= q_left and right <= q_right:\n",
    "        return tree[index].val             # 直接返回节点值\n",
    "    # 节点所在区间与 [q_left, q_right] 无关\n",
    "    if right < q_left or left > q_right:\n",
    "        return [0, 0]\n",
    "\n",
    "    mid = left + (right - left) // 2            # 左右节点划分点\n",
    "    left_index = index * 2 + 1                  # 左子节点的存储下标\n",
    "    right_index = index * 2 + 2                 # 右子节点的存储下标\n",
    "    res_left = [0, 0]\n",
    "    res_right = [0, 0]\n",
    "    if q_left <= mid:                           # 在左子树中查询\n",
    "        res_left = query_interval(tree, q_left, q_right, left_index)\n",
    "    if q_right > mid:                           # 在右子树中查询\n",
    "        res_right = query_interval(tree, q_left, q_right, right_index)\n",
    "\n",
    "    # 返回合并结果\n",
    "    return merge(res_left, res_right)\n",
    "\n",
    "    # 向上合并实现方法\n",
    "def merge(x, y):\n",
    "    if x[0] == y[0]: val = [x[0], x[1] + y[1]]\n",
    "    else: val = x if x[0] > y[0] else y\n",
    "    return val\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        tree = [Node() for _ in range(4 * n)]\n",
    "        build(tree, 0, 0, n - 1)\n",
    "        # 离散化处理\n",
    "        num_dict = dict()\n",
    "        nums_sort = sorted(nums)\n",
    "        for i in range(len(nums_sort)):\n",
    "            num_dict[nums_sort[i]] = i\n",
    "\n",
    "        # 构造线段树       \n",
    "\n",
    "        for num in nums:\n",
    "            index = num_dict[num]\n",
    "            val = query_interval(tree, 0, index - 1, 0)\n",
    "            if val[0] == 0:\n",
    "                val = [1, 1]\n",
    "            else:\n",
    "                val = [val[0] + 1, val[1]]\n",
    "            update_point(tree, index, val, 0)\n",
    "        return query_interval(tree, 0, len(nums_sort) - 1, 0)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\r\n",
    "        def bisect(r, func):\r\n",
    "            l = 0\r\n",
    "            while l < r:\r\n",
    "                mid = (l + r) // 2\r\n",
    "                if func(mid):\r\n",
    "                    l = mid + 1\r\n",
    "                else:\r\n",
    "                    r = mid\r\n",
    "            return l\r\n",
    "\r\n",
    "        len_nums = len(nums)\r\n",
    "        dp = [[] for _ in range(len_nums)]\r\n",
    "        cnt = [[0] for _ in range(len_nums + 1)]\r\n",
    "        dp[0].append(nums[0])\r\n",
    "        cnt[0].append(1)\r\n",
    "\r\n",
    "        length = 0\r\n",
    "\r\n",
    "        for i in range(1, len_nums):\r\n",
    "            if dp[length][-1] < nums[i]:\r\n",
    "                length += 1\r\n",
    "                dp[length].append(nums[i])\r\n",
    "                j = bisect(len(dp[length - 1]), lambda x: dp[length - 1][x] >= nums[i])\r\n",
    "                cnt[length].append(cnt[length - 1][-1] - cnt[length - 1][j])\r\n",
    "            else:\r\n",
    "                k = bisect(length, lambda x: dp[x][-1] < nums[i])\r\n",
    "                dp[k].append(nums[i])\r\n",
    "                j = bisect(len(dp[k - 1]), lambda x: dp[k - 1][x] >= nums[i])\r\n",
    "                if k > 0:\r\n",
    "                    cnt[k].append(cnt[k - 1][-1] - cnt[k - 1][j] + cnt[k][-1])\r\n",
    "                else:\r\n",
    "                    cnt[k].append(cnt[k][-1] + 1)\r\n",
    "        return cnt[length][-1]\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 线段树的节点类\n",
    "class Node:\n",
    "    def __init__(self, val=[0, 1]):\n",
    "        self.left = -1                              # 区间左边界\n",
    "        self.right = -1                             # 区间右边界\n",
    "        self.val = val \n",
    "\n",
    "def build(tree, node, left, right):\n",
    "    tree[node].left = left\n",
    "    tree[node].right = right\n",
    "    if left == right:                           # 叶子节点，节点值为对应位置的元素值\n",
    "        tree[node].val = [0, 0]\n",
    "        return\n",
    "\n",
    "    mid = left + (right - left) // 2            # 左右节点划分点\n",
    "    left_node = node * 2 + 1                  # 左子节点的存储下标\n",
    "    right_node = node * 2 + 2                 # 右子节点的存储下标\n",
    "    build(tree, left_node, left, mid)         # 递归创建左子树\n",
    "    build(tree, right_node, mid + 1, right)   # 递归创建右子树\n",
    "\n",
    "    tree[node].val = merge(\n",
    "        tree[left_node].val, tree[right_node].val)   # 向上更新节点的区间值\n",
    "\n",
    "    # 单点更新实现方法：将 nums[i] 更改为 val，节点的存储下标为 index\n",
    "def update_point(tree, i, val, node):\n",
    "    left = tree[node].left\n",
    "    right = tree[node].right\n",
    "\n",
    "    if left == i and right == i:\n",
    "        tree[node].val = merge(tree[node].val, val)\n",
    "        return\n",
    "\n",
    "    mid = left + (right - left) // 2   # 左右节点划分点\n",
    "    left_node = node * 2 + 1         # 左子节点的存储下标\n",
    "    right_node = node * 2 + 2        # 右子节点的存储下标\n",
    "    if i <= mid:                       # 在左子树中更新节点值\n",
    "        update_point(tree, i, val, left_node)\n",
    "    else:                              # 在右子树中更新节点值\n",
    "        update_point(tree, i, val, right_node)\n",
    "\n",
    "    tree[node].val = merge(\n",
    "        tree[left_node].val, tree[right_node].val)   # 向上更新节点的区间值\n",
    "\n",
    "    # 区间查询实现方法：在线段树中搜索区间为 [q_left, q_right] 的区间值\n",
    "\n",
    "def query(tree, q_left, q_right, node):\n",
    "    left = tree[node].left\n",
    "    right = tree[node].right\n",
    "\n",
    "    # 节点所在区间被 [q_left, q_right] 所覆盖\n",
    "    if left >= q_left and right <= q_right:\n",
    "        return tree[node].val             # 直接返回节点值\n",
    "    # 节点所在区间与 [q_left, q_right] 无关\n",
    "    if right < q_left or left > q_right:\n",
    "        return [0, 0]\n",
    "\n",
    "    mid = left + (right - left) // 2            # 左右节点划分点\n",
    "    left_node = node * 2 + 1                  # 左子节点的存储下标\n",
    "    right_node = node * 2 + 2                 # 右子节点的存储下标\n",
    "    res_left = [0, 0]\n",
    "    res_right = [0, 0]\n",
    "    if q_left <= mid:                           # 在左子树中查询\n",
    "        res_left = query(tree, q_left, q_right, left_node)\n",
    "    if q_right > mid:                           # 在右子树中查询\n",
    "        res_right = query(tree, q_left, q_right, right_node)\n",
    "\n",
    "    # 返回合并结果\n",
    "    return merge(res_left, res_right)\n",
    "\n",
    "    # 向上合并实现方法\n",
    "def merge(x, y):\n",
    "    if x[0] == y[0]: val = [x[0], x[1] + y[1]]\n",
    "    else: val = x if x[0] > y[0] else y\n",
    "    return val\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        tree = [Node() for _ in range(4 * n)]\n",
    "        build(tree, 0, 0, n - 1)\n",
    "        # 离散化处理\n",
    "        num_dict = dict()\n",
    "        nums_sort = sorted(nums)\n",
    "        for i in range(len(nums_sort)):\n",
    "            num_dict[nums_sort[i]] = i\n",
    "\n",
    "        # 构造线段树       \n",
    "\n",
    "        for num in nums:\n",
    "            index = num_dict[num]\n",
    "            val = query(tree, 0, index - 1, 0)\n",
    "            if val[0] == 0:\n",
    "                val = [1, 1]\n",
    "            else:\n",
    "                val = [val[0] + 1, val[1]]\n",
    "            update_point(tree, index, val, 0)\n",
    "        return query(tree, 0, len(nums_sort) - 1, 0)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        stk = []    # int\n",
    "        ls = []     # deque\n",
    "        vals = []   # deque\n",
    "        for i in nums:\n",
    "            p = bisect_left(stk,i)\n",
    "            if p<len(stk):\n",
    "                stk[p] = i \n",
    "                ls[p].appendleft(i)\n",
    "                    \n",
    "            else:\n",
    "                stk.append(i)\n",
    "                ls.append(deque([i]))\n",
    "                vals.append(deque([0]))\n",
    "            valp = vals[p]\n",
    "            if p==0:\n",
    "                valp.appendleft(valp[0]+1)\n",
    "            else:\n",
    "                prev = p-1\n",
    "                prevls = ls[prev]\n",
    "                preval = vals[prev]\n",
    "                while(prevls and prevls[-1]>=i):\n",
    "                    prevls.pop()\n",
    "                    preval.pop()\n",
    "                valp.appendleft(preval[0]-preval[-1]+valp[0])\n",
    "        return vals[-1][0]-vals[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        stk = []    # int\n",
    "        sums = []   # int\n",
    "        ls = []     # deque\n",
    "        vals = []   # deque\n",
    "        for i in nums:\n",
    "            p = bisect_left(stk,i)\n",
    "            if p<len(stk):\n",
    "                stk[p] = i \n",
    "                ls[p].appendleft(i)\n",
    "                    \n",
    "            else:\n",
    "                stk.append(i)\n",
    "                ls.append(deque([i]))\n",
    "                sums.append(0)\n",
    "                vals.append(deque())\n",
    "\n",
    "            if p==0:\n",
    "                sums[p]+=1\n",
    "                vals[p].appendleft(1)\n",
    "            else:\n",
    "                prev = p-1\n",
    "                prevls = ls[prev]\n",
    "                preval = vals[prev]\n",
    "                while(prevls and prevls[-1]>=i):\n",
    "                    prevls.pop()\n",
    "                    sums[prev] -= preval.pop()\n",
    "                sums[p]+=sums[p-1]\n",
    "                vals[p].appendleft(sums[p-1])\n",
    "        # print(stk)\n",
    "        # print(ls)\n",
    "        # print(sums)\n",
    "        # print(vals)\n",
    "        return sums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        stk = []    # int\n",
    "        ls = []     # deque\n",
    "        vals = []   # deque\n",
    "        for i in nums:\n",
    "            p = bisect_left(stk,i)\n",
    "            if p<len(stk):\n",
    "                stk[p] = i \n",
    "                ls[p].appendleft(i)\n",
    "                    \n",
    "            else:\n",
    "                stk.append(i)\n",
    "                ls.append(deque([i]))\n",
    "                vals.append(deque([0]))\n",
    "\n",
    "            if p==0:\n",
    "                vals[p].appendleft(vals[p][0]+1)\n",
    "            else:\n",
    "                prev = p-1\n",
    "                prevls = ls[prev]\n",
    "                preval = vals[prev]\n",
    "                while(prevls and prevls[-1]>=i):\n",
    "                    prevls.pop()\n",
    "                    preval.pop()\n",
    "                vals[p].appendleft(preval[0]-preval[-1]+vals[p][0])\n",
    "        return vals[-1][0]-vals[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumberOfLIS(self, nums: List[int]) -> int:\n",
    "        dp=defaultdict(Counter)\n",
    "        dp[-1][-inf]=1\n",
    "        seq = []\n",
    "        for num in nums:\n",
    "            idx = bisect.bisect_left(seq, num)\n",
    "            if idx == len(seq):\n",
    "                seq.append(num)\n",
    "            else:\n",
    "                seq[idx] = num\n",
    "            # dpdp[idx][num]是指seq中序号为idx即以val结尾的、长度为idx的元素对应的递增子序列个数，它等于所有比它小的idx-1的个数之和。\n",
    "            dp[idx][num]+=sum([ dp[idx-1][val] for val in dp[idx-1] if val<num])\n",
    "        # print(dp)\n",
    "        return sum(dp[len(seq)-1].values())"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
